/*
   This program implements KNN, the K-Nearest-Neighbors algorithm.
   Each thread finds K nearest neighbors, and sorts them.
   In a second stage, we choose the first K neighbors out of all the
   possible candidates.

   Usage: KNN num_threads num_points num_K
    - num_threads is the number of threads that we will be using.
    - num_points is the total number of points that we will be using.
    - num_K is the 'K' in the KNN algorithm.

    When benchmarking, make sure to use a 'num_points' that is much larger than
    the parameter 'num_k'.
 */

#include <stdio.h> 
#include <stdlib.h> 
#include <math.h> 
#include "timetools.h"

extern "C" {
//============================ BEGIN INPUT SIZE ==============================//
// Number of points in our universe.
long NUM_POINTS;

// The number of K nearest neighbors that we shall consider
long NUM_K;
//============================== END INPUT SIZE ==============================//

// Size of the largest X and Y coordinates:
#define LARGEST_X 32766
#define LARGEST_Y 32766

// The size of the buffer of private points:
long NUM_PRIVATE_POINTS;

// The X coordinate of the points:
long* points_X;

// The Y coordinate of the points:
long* points_Y;

// The buffer where each thread will keep their nearest points:
long* private_X;
long* private_Y;

// The point that must be found:
long pivot_x;
long pivot_y;

/*
   This function initializes an array with random characters. Each thread is
   in charge of initializing one block of the array.
 */
void initArray(long* points_X, long* points_Y, int num_points) {
  int i;
  for (i = 0; i < num_points; i++) {
    long x = random() % LARGEST_X;
    long y = random() % LARGEST_Y;
    points_X[i] = x;
    points_Y[i] = y;
  }
}

double distance(int x, int y, int xx, int yy) {
  return sqrt(abs(xx - x) * abs(xx - x) + abs(yy - y) * abs(yy - y));
}

int j_is_closer_than_i(long* array_X, long* array_Y, int i, int j,
    long point_x, long point_y) {
  double distance_i = distance(array_X[i], array_Y[i], point_x, point_y);
  double distance_j = distance(array_X[j], array_Y[j], point_x, point_y);
  return distance_j < distance_i;
}

/*
   This function implements the KNN algorithm.
 */
 
 
const unsigned long PAGESZ = 4096; //bytes
const unsigned long PAGEMSK = ~(4095);

void* get_page(void* array, int i) {
  unsigned long page = (unsigned long) array;
  page = page + i*PAGESZ;
  page = page & (~(4095));
  return (void*) page;
}

void KNN() {
  int i, j;

  // Sort the points by distance:
  for (i = 0; i < NUM_POINTS - 1; i++) {
    for (j = i + 1; j < NUM_POINTS; j++) {
      if (j_is_closer_than_i(points_X, points_Y, i, j, pivot_x, pivot_y)) {
        long tmp = points_X[i];
        points_X[i] = points_X[j];
        points_X[j] = tmp;
        tmp = points_Y[i];
        points_Y[i] = points_Y[j];
        points_Y[j] = tmp;
      }
    }
  }
  // Copy the K nearest points to the private buffer:
  for (i = 0; i < NUM_K; i++) {
    private_X[i] = points_X[i];
    private_Y[i] = points_Y[i];
  }
}

void print_first_k(long* array_x, long* array_y, const int K) {
  int i;
  for (i = 0; i < K; i++) {
    printf("(%ld, %ld - %.2f) ", array_x[i], array_y[i],
        distance(array_x[i], array_y[i], pivot_x, pivot_y));
  }
  printf("\n");
}

int main (int argc, char *argv[]) { 

  int t; 

  srand(42);

  if (argc != 3) {
    fprintf(stderr, "Syntax: %s num_points num_K\n", argv[0]);
    fprintf(stderr, "- num_points >> num_K\n");
    return -1;
  }

    int i, j;
    // Read input arguments:
    NUM_POINTS  = atoi(argv[1]);
    NUM_K  = atoi(argv[2]);

    if (NUM_POINTS < NUM_K) {
        fprintf(stderr, "Invalid arguments. Expected num_points > num_k\n");
        return -1;
    }

    // Initialize the array of points:
    points_X = (long*) malloc(NUM_POINTS * sizeof(long));
    points_Y = (long*) malloc(NUM_POINTS * sizeof(long));
    initArray(points_X, points_Y, NUM_POINTS);

    // Initialize the private buffer:
    private_X = (long*) malloc(NUM_K * sizeof(long));
    private_Y = (long*) malloc(NUM_K * sizeof(long));

    // Initialize the pivot:
    pivot_x = 0;
    pivot_y = 0;
#ifdef ENABLE_OUTPUT
    // Initialize the array of KNN threads:
    timespec startTime, endTime;
    readTime(&startTime);
#endif
    KNN();

    // Sort the points in the private buffers by distance:
    for (i = 0; i < NUM_K - 1; i++) {
      for (j = i + 1; j < NUM_K; j++) {
        if (j_is_closer_than_i(private_X, private_Y, i, j, pivot_x, pivot_y)) {
          long tmp = private_X[i];
          private_X[i] = private_X[j];
          private_X[j] = tmp;
          tmp = private_Y[i];
          private_Y[i] = private_Y[j];
          private_Y[j] = tmp;
        }
      }
    }
#ifdef ENABLE_OUTPUT
    readTime(&endTime);
    const double elapsedTime = timeDiff(startTime, endTime);
    printf("SIZE %ld %ld\nTIME %f\n", NUM_POINTS, NUM_K, elapsedTime);
#endif
    // Print the results:
    // printf("Universe of points:\n");
    // print_first_k(points_X, points_Y, NUM_POINTS);
    //printf("K nearest points:\n");
    //print_first_k(private_X, private_Y, NUM_K);

	return 0;
	
}

}
